package a2022.a20220519;

import java.util.Arrays;

/**
 * @author lenovo
 * @date 2022/5/20
 */
public class a {
    // [[1,2],[2,3],[0,1],[3,4]]
    // [1,3,0,-1]
    public static void main(String[] args) {
        int[][] intervals = new int[4][2];
        intervals[0][0] = 1;
        intervals[0][1] = 2;
        intervals[1][0] = 2;
        intervals[1][1] = 3;
        intervals[2][0] = 0;
        intervals[2][1] = 1;
        intervals[3][0] = 3;
        intervals[3][1] = 4;
        int[] rightInterval = findRightInterval(intervals);
        System.out.println(Arrays.toString(rightInterval));
    }


//    public static int[] findRightInterval(int[][] intervals) {
//        int[] start = new int[intervals.length];
//        int[] end = new int[intervals.length];
//        int[] MyCalendarThree = new int[intervals.length];
//        for (int i = 0; i < intervals.length; i++) {
//            start[i] = intervals[i][0];
//            end[i] = intervals[i][1];
//        }
//        for (int i = 0; i < end.length; i++) {
//            MyCalendarThree[i] = -1;
//            int z = Integer.MAX_VALUE;
//            for (int j = 0; j < start.length; j++) {
//                int y = -1, x = -1;
//                if (end[i] <= start[j]) {
//                    if (z >= start[j]) {
//                        if (x == -1) {
//                            x = start[j];
//                            y = j;
//                            MyCalendarThree[i] = j;
//                        }
//                        if (x > start[j]) {
//                            x = start[j];
//                            y = j;
//                            MyCalendarThree[i] = j;
//                        }
//                    }
//                    z = start[j];
//                }
//
//            }
//        }
//        return MyCalendarThree;
//    }


    public static int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] startIntervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            startIntervals[i][0] = intervals[i][0];
            startIntervals[i][1] = i;
        }


//        Comparator comparator = new Comparator() {
//            @Override
//            public int compare(Object o, Object t1) {
//                return o1[0] - o2[0];
//            }
//
//            @Override
//            public boolean equals(Object o) {
//                return false;
//            }
//        };
        Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            int target = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (startIntervals[mid][0] >= intervals[i][1]) {
                    target = startIntervals[mid][1];
                      right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            ans[i] = target;
        }
        return ans;
    }
}
